package _dp_base;

import java.util.ArrayList;
import java.util.List;

/**
 * 300. 最长递增子序列
 */
public class No300 {
    private int[] nums;
    private int[][] cache;
    /*
      一、选或不选
     */

    /**
     * 1. 递归
     */
    public int lengthOfLIS11(int[] nums) {
        int n = nums.length;
        this.nums = new int[n + 1];
        System.arraycopy(nums, 0, this.nums, 0, nums.length);
        this.nums[n] = Integer.MAX_VALUE;
        this.cache = new int[n][n + 1];
        return dfs(n - 1, n);
    }

    private int dfs(int i, int j) {
        if (i < 0) return 0;
        if (cache[i][j] != 0) return cache[i][j];
        else if (nums[i] >= nums[j]) return cache[i][j] = dfs(i - 1, j);
        else return cache[i][j] = Math.max(dfs(i - 1, j), dfs(i - 1, i) + 1);
    }

    /**
     * 2. 迭代
     */
    public int lengthOfLIS12(int[] nums) {
        int n = nums.length;
        this.nums = new int[n + 1];
        System.arraycopy(nums, 0, this.nums, 0, nums.length);
        this.nums[n] = Integer.MAX_VALUE;

        int[][] f = new int[n + 1][n + 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n + 1; j++) {
                if (this.nums[i] >= this.nums[j]) f[i + 1][j + 1] = f[i][j + 1];
                else f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i][i + 1] + 1);
            }
        }
        return f[n][n + 1];
    }

    /**
     * 4. 空间优化
     */
    public int lengthOfLIS14(int[] nums) {
        int n = nums.length;
        this.nums = new int[n + 1];
        System.arraycopy(nums, 0, this.nums, 0, nums.length);
        this.nums[n] = Integer.MAX_VALUE;

        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            for (int j = n; j >= 0; j--) {
                if (this.nums[i] < this.nums[j]) {
                    f[j + 1] = Math.max(f[j + 1], f[i + 1] + 1);
                }
            }
        }
        return f[n + 1];
    }

    /*
      二、枚举选哪个
     */

    /**
     * 1. 递归
     */
    public int lengthOfLIS21(int[] nums) {
        int n = nums.length;
        this.nums = nums;

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(dfs(i), answer);
        }
        return answer;
    }

    private int dfs(int i) {
        int maxLen = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                int preMaxLen = dfs(j);
                if (preMaxLen + 1 > maxLen) {
                    maxLen = preMaxLen + 1;
                }
            }
        }
        return maxLen;
    }

    /**
     * 2. 迭代
     */
    public int lengthOfLIS22(int[] nums) {
        int n = nums.length;

        int answer = 0;
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[j] + 1 > f[i]) {
                        f[i] = f[j] + 1;
                    }
                }
            }
            answer = Math.max(f[i], answer);
        }

        return answer;
    }

    /*
      三、贪心 + 二分查找
     */

    /**
     * 1. 额外空间
     */
    public int lengthOfLIS31(int[] nums) {
        ArrayList<Integer> g = new ArrayList<>();
        for (int num : nums) {
            int index = lowerBound(g, num);
            if (index == g.size()) g.add(num); // >=x 的 g[index] 不存在
            else g.set(index, num);
        }
        return g.size();
    }

    /**
     * 2. 原地修改
     */
    public int lengthOfLIS32(int[] nums) {
        int ng = 0; // g 的长度
        for (int x : nums) {
            int index = lowerBound(nums, ng, x);
            nums[index] = x;
            if (index == ng) // >=x 的 g[index] 不存在
                ++ng;
        }
        return ng;
    }

    // 开区间写法
    private int lowerBound(List<Integer> g, int target) {
        int left = -1, right = g.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (g.get(mid) < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }

    // 开区间写法
    private int lowerBound(int[] nums, int right, int target) {
        int left = -1; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }
}
